#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <unordered_map>
using namespace std;
template<class T>
class UnionFindSet
{
public:
    //初始化并查集:刚开始都是-1.
    UnionFindSet(const vector<T>& v)
        :_ufs(v.size(), -1)
    {
        for (int i = 0; i < v.size(); i++)
        {
            _indexMap[v[i]] = i;
        }
    }

    //查找元素所在集合:
    //在查找集合结点的时候进行压缩.
    //+压缩路径:
    int FindRoot(const T& x)
    {
        int root = _indexMap[x];
        //遍历到值为负数就是根结点.
        while (_ufs[root] >= 0)
        {
            //不停迭代下标查询.
            root = _ufs[root];
        }

        //一般数据量少不需要压缩.
        // while(_ufs[x] >= 0)
        // {
        //     int parent = _ufs[x];
        //     _ufs[x] = root;
        //     x = parent;
        // }
        return root;
    }

    //递归方法查找 + 压缩;
    // int _FindRoot(int x)
    // {
    //     //return _ufs[x] < 0 ? x : _FindRoot(_ufs[x]);
    //     int parent = x;
    //     if(_ufs[x] >= 0)
    //     {
    //         parent = _FindRoot(_ufs[x]);
    //         _ufs[x] = parent;
    //     }
    // }

    //判断两个元素是否在同一个集合中.
    bool InSameSet(const T& x1, const T& x2)
    {
        //检查两个元素根结点是否同一个即可.
        return FindRoot(x1) == FindRoot(x2);
    }

    //合并两个元素所在集合.
    bool UnionSet(const T& x1, const T& x2)
    {
        int parent1 = FindRoot(x1); int parent2 = FindRoot(x2);
        if (parent1 == parent2)
            return false;

        if (_ufs[parent1] > _ufs[parent2])
        {
            swap(parent1, parent2);
        }

        _ufs[parent1] += _ufs[parent2];
        _ufs[parent2] = parent1;
        return true;
    }


    //查询集合里面的个数:
    int GetNum()
    {
        int count = 0;
        for (const int& val : _ufs)
        {
            if (val < 0)
                count++;
        }
        return count;
    }


private:
    vector<int> _ufs;
    //原来标记数据T的处于哪个集合里面.
    unordered_map<T, int> _indexMap;
};

int main() {
    vector<string> v = { "张三", "李四", "王五", "赵六", "田七", "周八", "吴九" };
    UnionFindSet<string> ufs(v);
    cout << ufs.GetNum() << endl; //7

    ufs.UnionSet("张三", "李四");
    ufs.UnionSet("王五", "赵六");
    cout << ufs.GetNum() << endl; //5

    ufs.UnionSet("张三", "赵六");
    cout << ufs.GetNum() << endl; //4

    return 0;
}

